1. Field of the Invention
The present invention relates to the field of finite-field multipliers, and more particularly, to a general finite-field multiplier and the method of the same.
2. Description of Related Art
A finite-field element is a value with a fixed bit number, for example, an element has four bits, and thus 16 values are possibly formed. Since in the encryption or error correction (such as Reed-Solomon code, abbreviated as RS code), signals are necessary to be coded so that the coded value can be represented by a mathematical polynomial p(x) and then a decoded operation can be used. Therefore, each fixed bit value must be given a representation symbol. Furthermore, the AND and XOR operations can be performed between these symbols for generating another symbols. For example, four bits are used as a symbol of an element. When AND or XOR operations are performed between different elements, at most only 16 results may be generated. Therefore, the set of these symbols having four bits can be used as a finite field. Through the operations of these elements in the finite field, the data can be encrypted or decrypted, and coded or decoded.
For the addition of two elements, it can be implemented by an XOR gate. However, to design the circuit for the multiplying operation of two elements is more complex. Conventionally, the multiplying operation is performed by a finite-field multiplier formed by, for example, a Berlekamp multiplier and two basis converters. This finite-field multiplier is known as a bit-serial multiplier. Therefore, the circuit structure is very simple. However, an obvious disadvantage is that the speed of multiplying is very slow. Moreover, the specification of p(x) is formed by a constant form, and thus, it can not be adjusted according to the practical requirement.
In order to avoid the problem in that the speed of the multiplier is too slow, a parallel construction may be used. This parallel multiplier primarily utilizes a Mastrovito finite-field multiplying operation, wherein one of two elements to be multiplied is at first converted to a matrix, and then vector-multiplied with the second element for generating a desired value. Therefore, the parallel multiplier is primarily formed by AND gates and XOR gates, and the components thereof are increased with the highest order of m. Therefore, the complexity of the hardware is O(m2).
As such, the finite-field multiplier is improved from the conventional bit-serial multiplier into a parallel multiplier. Most of the design specification of the multiplier is constant. When the specification of the p(x) is changed, the conventional constant-type p(x) can not be used. Therefore, Hasan disclosed an adjustable bit-serial systolic finite-field multiplier, wherein the p(x) is changeable. FIG. 6 shows a bit-serial systolic matrix generator of a finite-field element multiplier disclosed by Hasan, which is provided primarily for receiving an element A=(a0,a1, . . . am-1) to generate a column vector for matrix operation, wherein columns 1˜m-1 will generate the column vector of the matrix, while the p(x) is changeable and can control the bit number of an element. The circuit structure of a combination component Q in this multiplier is illustrated in FIG. 7. There are three input values, wherein pin is a series of coefficients input to the p(x). As the first bit value of the symbol is received, qin will input an 1, otherwise a 0, while ain will generate the operation value in the matrix. The operation of the circuit is listed in the following:
if qin=1
then
aout=r; r=ain;
else
gout=gtemp; gtemp=gin;
qout=qtemp; qtemp=qin;
FIG. 8 shows a complete functional module of this multi-functional bit-serial multiplier. The circuit of the internal element W thereof is illustrated in FIG. 9. Therefore, in this multiplier, element Q is used as a synthetic circuit for embodying required values in the matrix operation, and then, together with the element W and several dozens of flip-flops, the circuit of the multiplier can be accomplished. However, this circuit is only suitable for a finite-field multiplier with a constant length. In comparing with the aforesaid conventional multiplier with a constant p(x), there are too many logic gates used. Therefore, the disadvantage is that a large latency is employed in the data output of the circuit.
In the aforementioned conventional bit-serial multiplier, as a bit value is received, the shifting and multiplying operations must be performed for generating a desired value. The time of shifting for a multiplying operation of two elements in the multiplier is related to the highest order of the p(x) or is related to the number of bits interpreting a symbol. When the highest order of p(X) becomes larger, although the conventional bit-serial multiplier has less logic gate delays, the output thereof is in a bit serial manner, which may cause a serious problem in the computation of a Reed-Solomon code algorithm. Therefore, it is desirable to provide an improved general finite-field multiplier device and the method of the same to mitigate and/or obviate the aforementioned problems.